/**
 * @program: LeetCode
 * @description: LeetCode : 91. 解码方法
 * @author: WXY
 * @create: 2023-01-06 12:42
 * @Version 1.0
 **/
public class Num091_numDecodings {
    public static int numDecodings1(String s) {
        if (s.length() == 0 || s == null) return 0;
        return process(s.toCharArray(), 0);
    }

    private static int process(char[] str, int i) {
        if (i == str.length) return 1;
        if (str[i] == '0') return 0;
        if (str[i] == '1') {
            int res = process(str, i + 1);
            if (i + 1 < str.length) {
                res += process(str, i + 2);
            }
            return res;

        }
        if (str[i] == '2') {
            int res = process(str, i + 1);
            if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
                res += process(str, i + 2);
            }
            return res;
        }
        return process(str, i + 1);
    }


    public static int numDecodings(String s) {
        if (s.length() == 0 || s == null) return 0;
        char[] str = s.toCharArray();
        int N = str.length;
        int[] dp = new int[N + 1];
        dp[N] = 1;
        for (int i = N - 1; i >= 0; i--) {
            if (str[i] == '0') {
                dp[i] = 0;
            } else if (str[i] == '1') {
                dp[i] = dp[i + 1];
                if (i + 1 < str.length) {
                    dp[i] += dp[i + 2];
                }
            } else if (str[i] == '2') {
                dp[i] = dp[i + 1];
                if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
                    dp[i] += dp[i + 2];
                }
            } else {
                dp[i] = dp[i + 1];
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        String s = "226";
        int i = numDecodings(s);
        System.out.println(i);
    }
}
